//树采用孩子-兄弟的二叉链表存储，按层次输出树的所有结点
#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode* firstChild;
    struct TreeNode* nextSibling;
} TreeNode;

// 队列节点结构体
typedef struct QueueNode {
    TreeNode* data;
    struct QueueNode* next;
} QueueNode;

// 创建新的队列节点
QueueNode* createQueueNode(TreeNode* value) {
    QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

// 创建空队列
QueueNode* createQueue() {
    return NULL;
}

// 判断队列是否为空
int isQueueEmpty(QueueNode* queue) {
    return queue == NULL;
}

// 入队操作
void enqueue(QueueNode** queue, TreeNode* value) {
    QueueNode* newNode = createQueueNode(value);
    if (*queue == NULL) {
        *queue = newNode;
    } else {
        QueueNode* temp = *queue;
        while (temp->next!= NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
}

// 出队操作
TreeNode* dequeue(QueueNode** queue) {
    if (isQueueEmpty(*queue)) {
        return NULL;
    }
    QueueNode* temp = *queue;
    TreeNode* value = temp->data;
    *queue = (*queue)->next;
    free(temp);
    return value;
}

// 按层次输出树的所有结点
void levelOrderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    QueueNode* queue = createQueue();
    enqueue(&queue, root);
    while (!isQueueEmpty(queue)) {
        TreeNode* current = dequeue(&queue);
        printf("%d ", current->val);
        TreeNode* child = current->firstChild;
        while (child!= NULL) {
            enqueue(&queue, child);
            child = child->nextSibling;
        }
    }
}

// 创建树节点
TreeNode* createTreeNode(int value) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode->val = value;
    newNode->firstChild = NULL;
    newNode->nextSibling = NULL;
    return newNode;
}

int main() {
    // 创建树
    TreeNode* root = createTreeNode(1);
    TreeNode* node2 = createTreeNode(2);
    TreeNode* node3 = createTreeNode(3);
    TreeNode* node4 = createTreeNode(4);
    TreeNode* node5 = createTreeNode(5);

    root->firstChild = node2;
    node2->nextSibling = node3;
    node2->firstChild = node4;
    node3->firstChild = node5;

    printf("Level order traversal: ");
    levelOrderTraversal(root);
    printf("\n");

    // 释放内存
    //...

    return 0;
}